/*
 * @lc app=leetcode id=322 lang=cpp
 *
 * [322] Coin Change
 */

bool cmp(const int a, const int b) {
    return b < a;
}
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int len = coins.size();
        if (len < 1) {
            return -1;
        }

        sort(coins.begin(), coins.end());
        int minCoin = coins[0];

        vector<int> memo(amount+1, -1);
        memo[0] = 0;

        for (int i=1; i<=amount; i++) {
            for (auto c : coins) {
                if (i >= c && memo[i-c] != -1) {
                    if (memo[i] == -1) {
                        memo[i] = memo[i-c]+1;
                    } else {
                        memo[i] = std::min(memo[i], memo[i-c]+1);
                    }
                }
            }
        }

        return memo[amount] == -1 ? -1 : memo[amount];
    }

};

